#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/**
 * 埃拉托色尼筛法：求小于等于n的所有素数
 * @param n: 上限值
 * @param prime_count: 输出参数，返回素数的个数
 * @return: 存储素数的动态数组（需调用者手动释放），失败返回NULL
 */
int* eratoshenes(int n, int* prime_count) {
    // 特殊情况处理：n<2时无素数
    if (n < 2) {
        *prime_count = 0;
        return NULL;
    }

    // 1. 创建筛选数组（对应Java的boolean[] ints）
    // 用calloc初始化，默认值为false，后续再将所有元素设为true
    bool* is_prime = (bool*)calloc(n + 1, sizeof(bool));
    if (!is_prime) {
        fprintf(stderr, "内存分配失败！\n");
        *prime_count = 0;
        return NULL;
    }

    // 初始化所有元素为true（Java的Arrays.fill(ints, true)）
    for (int i = 2; i <= n; i++) {
        is_prime[i] = true;
    }

    // 2. 筛选素数（核心逻辑与Java一致）
    // 先收集素数到临时列表（先统计个数，再分配数组，避免多次扩容）
    int count = 0;
    // 第一次遍历：统计素数个数
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            count++;
            // 标记当前素数的倍数为非素数（i<<1 等价于 i*2）
            for (int j = i << 1; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // 3. 存储素数到结果数组
    int* primes = (int*)malloc(count * sizeof(int));
    if (!primes) {
        fprintf(stderr, "内存分配失败！\n");
        free(is_prime);
        *prime_count = 0;
        return NULL;
    }

    int idx = 0;
    // 第二次遍历：将素数存入数组
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes[idx++] = i;
        }
    }

    // 释放筛选数组，设置输出参数
    free(is_prime);
    *prime_count = count;
    return primes;
}

// 测试主函数
int main() {
    int n = 20;
    int prime_count = 0;
    int* primes = eratoshenes(n, &prime_count);

    if (primes) {
        printf("小于等于%d的素数：[", n);
        for (int i = 0; i < prime_count; i++) {
            printf("%d", primes[i]);
            if (i != prime_count - 1) {
                printf(", ");
            }
        }
        printf("]\n");

        // 释放动态数组内存（避免内存泄漏）
        free(primes);
    } else {
        if (n < 2) {
            printf("小于%d的素数不存在！\n", n);
        } else {
            printf("素数计算失败！\n");
        }
    }

    return 0;
}